In data communications, a tailbiting trellis may be used to reduce overhead in convolutional codes that may be caused by returning the trellis to a known ending state. Terminating the encoded data with a known ending state ensures that the traceback to determine the output bits is started from the correct state with the correct cost value. The performance of the decoder generally degrades if the starting and ending states are unknown. However, a known ending state requires extra overhead since known bits need to be added to the transmitted signal to force the encoder to the known ending state. Tailbiting is a technique that forces the starting state to be the same as the ending state, without the penalty of the overhead bits.
In a tailbiting convolutional code, the input bits are generally grouped into blocks with a fixed block length. For each fixed length block of bits, the convolutional encoder is initialized with the final data bits of the code block. Thus, at the end of the block, the encoder is at the same state as the beginning of the block. However, the convolutional decoder in the receiver does not know the starting-and-ending state.
FIG. 1 shows an example of an encoder 10 with a code block length of N and a convolutional code rate of M/N, with a memory length of k. Input data bits x1x2 . . . xN are convolutionally encoded by encoder 10 to produce coded data y1y2 . . . ym. At any given time, encoder 10 has a state s1s2 . . . sk. After encoding bit xN, s1s2 . . . sk will represent the ending state of the encoded data block.
Since the beginning-and-ending state of coded data y1y2 . . . ym is unknown, decoding the convolutional code is more complicated. However, there will be a signal-to-noise gain since there is no rate loss penalty compared to a conventional convolutional code that forces the ending state (i.e., the “tail”) to a known state. In addition, all of the bits are protected equally, unlike the code with a known tail.
Generally, the optimum method for decoding tailbiting codes is to search through all possible trellis paths with the same initial and ending state, and choose the trellis path with the lowest cost or lowest metric (i.e., the most likely path). The initial state can be forced to a particular value by disallowing transitions from other states (e.g., in accordance with certain predetermined constraints), and the ending state can be forced to the same value as the initial state by starting the traceback from the state with the same value. This optimum decoding becomes prohibitively complex when a convolutional code with many states is used, as in IEEE Standards 802.11a, 802.11b, 802.11g, 802.11n, 802.16 and 802.20.
By exploiting the cyclic nature of the tailbiting code, a suboptimal decoding scheme with smaller decoding complexity can be used for decoding the convolutional codes. A received block of signals may be replicated, and one or more replicas may be concatenated with the received block and then decoded using a regular Viterbi algorithm (“Viterbi decoding”). Ideally, in such a scheme, the output bits repeat themselves with a period equal to the block length after a few cycles of Viterbi decoding. However, this convergence may not always happen, and as a result, the algorithm is suboptimal.
To prevent Viterbi decoding from entering into an infinite loop when the algorithm does not converge, a fixed number of cyclic concatenations may be decoded, and the output bits at the end used as an estimate of the transmitted bits (see, e.g., R. V. Cox, C. E. W. Sundberg, “An efficient adaptive circular Viterbi algorithm for decoding generalized tailbiting convolutional codes,” IEEE Transactions on Vehicular Technology, vol. 43, iss. 1, February 1994, pgs. 57-68). However, in this approach, the entire block of received signals is stored until the block is decoded. In a simplified alternative method, the stored code word is decoded twice, the output from the first decoding cycle is ignored, and the output from the second decoding cycle is retained as the decoded output (see, e.g., C. R. Cahn, “Viterbi Decoding with Tail Biting in the IEEE 802.16 Standard,” IEEE 802.16 Broadband Wireless Access Working Group, Aug. 15, 2001). Although the additional storage requirement of the aforementioned method can be satisfied in some cases by sharing memory from a deinterleaver (e.g., as is used in IEEE 802.11- and 802.16-compliant receivers), these approaches generally require more memory than conventional convolutional codes using an optimal decoding solution. In addition, due to the multiple decoding cycles, the Viterbi decoder 20, shown in FIG. 2, has to operate at a speed that is a multiple of the data rate.
A need therefore exists to simplify the operation of Viterbi decoders further, and without sacrificing performance and/or operational efficiencies, to keep up with ever-increasing demands for increased network speeds, performance and capabilities.